package com.future;

import com.future.util.TreeNode;

import static com.future.mashibing.class06.TraversBinaryTree.middleOrder;
import static com.future.mashibing.class06.TraversBinaryTree.preOrder;

/**
 * 给定一棵树的前序遍历 preorder
 * 与中序遍历  inorder。请构造二叉树并返回其根节点。
 * <p>
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_105 {

    public static void main(String[] args) {
        int[] preorder = {1, 2, 4, 5, 3, 6, 7};
        int[] inorder = {4, 2, 5, 1, 3, 7, 6};
        TreeNode head = buildTree(preorder, inorder);
        preOrder(head);
        System.out.println();
        middleOrder(head);
    }

    /**
     * @param preorder
     * @param inorder
     * @return
     */
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    /**
     * 根据前序、中序构建二叉树
     * 思路：1、pre的第一个下标s1是根
     * 2、根据第一个根节点值，从in中找到左右子树分割点
     * example:
     * pre:{1,2,4,5,3,6,7}
     * in: {4,2,5,1,3,7,6}
     * (1) 根 1 建立节点head = new Node(1)
     * (2) 从in知道左子树{4,2，5},右子树{3,7,6}
     * 反推回去，pre 左子树{2,4,5}，右子树{3,6,7}
     * 递归 pre1 = {2，4,5},in1 = {4,2,5}
     * 递归 pre2 = {3,6,7}, in2 = {3,7,6}
     * ........
     *
     * @param preOrder 前序遍历数组
     * @param s1       前序开始下标
     * @param e1       前序结束下标
     * @param inOrder  中序遍历数组
     * @param s2       中序开始下标
     * @param e2       中序结束下标
     * @return 返回二叉树
     */
    private static TreeNode build(int[] preOrder, int s1, int e1, int[] inOrder, int s2, int e2) {
        if (s1 > e1) {
            // preOder=[1,2,3]
            // inOder=[1,2,3]
            return null;
        }
        // 新建节点
        TreeNode head = new TreeNode(preOrder[s1]);
        if (s1 == e1) {
            return head;
        }
        int find = s2;
        while (inOrder[find] != preOrder[s1]) {
            find++;
        }
        // 递归创建左子树
        head.left = build(preOrder, s1 + 1, s1 + (find - s2), inOrder, s2, find - 1);
        // 递归创建右子树
        head.right = build(preOrder, s1 + (find - s2) + 1, e1, inOrder, find + 1, e2);
        return head;
    }


    private static int getRootIndex(int[] inorder, int val) {
        if (inorder == null || inorder.length <= 1) {
            return 0;
        }
        for (int i = 0; i < inorder.length; i++) {
            if (val == inorder[i]) {
                return i;
            }
        }
        return 0;
    }

}
